#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <math.h>
using namespace std;
void rotate(vector<int>& nums, int k)
{
	
		k = k % nums.size();
		reverse(nums.begin(), nums.end());
		reverse(nums.begin(), nums.begin() + k);
		reverse(nums.begin()+k, nums.end());
}
struct ListNode {
	int val;
	ListNode* next;
	ListNode* random;
	ListNode(int x) : val(x), next(NULL),random(NULL) {}
};
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
{
	ListNode* curA = headA, * curB = headB;
	int lenthA = 0, lenthB = 0;
	while (curA)
	{
		lenthA++;
		curA = curA->next;
	}
	while (curB)
	{
		lenthB++;
		curB = curB->next;
	}
	int gap = abs(lenthA - lenthB);
	ListNode* longlist = headA, * shortlist = headB;
	if (lenthA < lenthB)
	{
		longlist = headB;
		shortlist = headA;
	}
	while (gap--)
	{
		longlist = longlist->next;
	}
	while (longlist != shortlist)
	{
		longlist = longlist->next;
		shortlist = shortlist->next;
	}
	return longlist;
}
ListNode* Middle(ListNode* A)
{
	ListNode* fast = A, * slow = A;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}
void Reverse(ListNode* A)
{
	ListNode* pre = nullptr, *cur = A, *next = A->next;
	while (cur)
	{
		cur->next = pre;
		pre = cur;
		cur = next;
		if(next)
		next = next->next;
	}
}
bool chkPalindrome(ListNode* A) 
{
	ListNode* mid = Middle(A);
	ListNode* head = A;
	ListNode* tail = A;
	while (tail->next)
	{
		tail = tail->next;
	}
	Reverse(mid);
	while (tail)
	{
		if (tail->val != head->val)
		{
			return false;
		}
		head = head->next;
		tail = tail->next;
	}
	return true;
}
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) 
{
	ListNode* fast = pListHead, * slow = pListHead;
	while (k--)
	{
		if (fast == nullptr)
		{
			return nullptr;
		}
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow;
}
bool hasCycle(ListNode* head) 
{
	ListNode* fast = head, * slow = head;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
		if (fast == slow)
		{
			return true;
		}
	}
	return false;
}
ListNode* detectCycle(ListNode* head) 
{
	ListNode* fast = head, * slow = head;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
		if (fast == slow)
		{
			while (head != fast)
			{
				head = head->next;
				fast = fast->next;
			}
			return head;
		}
	}
	return nullptr;
}
typedef ListNode Node;
Node* copyRandomList(Node* head) 
{
	Node* cur = head;
	while (cur)
	{
		Node* copy = new Node(cur->val);
		Node* next = cur->next;
		cur->next = copy;
		copy->next = next;
		cur = next;
	}
	cur = head;
	while (cur)
	{
		Node* copy = cur->next;
		if (cur->random == nullptr)
		{
			copy->random = nullptr;
		}
		else
		copy->random = cur->random->next;
		cur = copy->next;
	}
	Node* copyhead = nullptr;
	cur = head;
	while (cur)
	{
		Node* copy = cur->next;
		Node* next = copy->next;
		if (copyhead == nullptr)
		{
			copyhead = copy;
		}
		cur->next = next;
		if (next == nullptr)
			copy->next = nullptr;
		else
		    copy->next = next->next;
		cur = next;
	}
	return copyhead;
}
bool isValid(string s) 
{
	stack<char> st;
	for (auto e : s)
	{
		if (e == '(' || e == '[' || e == '{')
		{
			st.push(e);
		}
		else
		{
			if (st.empty())
			{
				return false;
			}
			char top = st.top();
			st.pop();
			if ((top == '(' && e != ')') || (top == '[' && e != ']') || (top == '{' && e != '}'))
			{
				return false;
			}
		}
	}
	return st.empty();
}
int main()
{
	ListNode* n1 = new ListNode(1);
	ListNode* n2 = new ListNode(2);
	ListNode* n3 = new ListNode(2);
	ListNode* n4 = new ListNode(1);
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	bool ret = chkPalindrome(n1);
	
	return 0;
}